package 链表;

/**
 * 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点
 * 例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点
 * User: zhaixiaolong Date:2024/1/3 17:15 ProjectName: algorithm Version:
 */
public class 倒数第k个节点 {

    /**
     * 初始化链表
     *
     * @return
     */
    public static Node initData() {
        Node node1 = new Node();
        node1.value = 1;
        Node node2 = new Node();
        node2.value = 2;
        Node node3 = new Node();
        node3.value = 3;
        Node node4 = new Node();
        node4.value = 4;
        Node node5 = new Node();
        node5.value = 5;
        Node node6 = new Node();
        node6.value = 6;

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        return node1;
    }

    public static void main(String[] args) {
        Node head = initData();
        System.out.println(getK(head, 3).value);
    }

    public static Node getK(Node head, int k) {
        Node pre = head;
        while (k != 0) {
            k--;
            pre = pre.next;
        }
        Node after = head;
        while (pre.next != null) {
            pre = pre.next;
            after = after.next;
        }
        return after.next;
    }

    public Node getKthFromEnd(Node head, int k) {
        if (head == null) {
            return null;
        }
        Node preNode = head, afterNode = head;
        int step = 0;
        while (preNode != null) {
            preNode = preNode.next;
            step++;
            if (step > k) {
                afterNode = afterNode.next;
            }
        }
        return afterNode;
    }

}
